#include "List.h"

List::List():size(0)
{
    head = new Node(0);
}

List::List(const List &l)
{
    size = l.size;
    head = new Node(0);
    Node* tp = head;
    Node* np = l.head->next;
    while(np)
    {
        Node *newnode = new Node(np->value);
        tp->next = newnode;
        tp = tp->next;
        np = np->next;
    }

}

List &List::operator=(const List &l)
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        delete head;
        head = nextNode;
    }
     size = l.size;
    head = new Node(0);
    Node* tp = head;
    Node* np = l.head->next;
    while(np)
    {
        Node *newnode = new Node(np->value);
        tp->next = newnode;
        tp = tp->next;
        np = np->next;
    }

}

List::~List()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        delete head;
        head = nextNode;
    }
}

void List::InsertTail(const ElementType &element)
{
    Node *tp = head;
    while(tp->next)
        tp = tp->next;
    tp->next = new Node(element);
    size++;
}

void List::InsertHead(const ElementType &element)
{
    Node *node = new Node(element);
    node->next = head->next;
    head->next = node;
    size++;
}

void List::InsertByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
        return;
    Node *tp = head;
    for(int i = 0;i < index;i++)
    {
        tp = tp->next;
    }
    Node *node = new Node(element);
    node->next = tp->next;
    tp->next = node;
    size++;
    
}

void List::RemoveByIndex(size_t index)
{
    if(index >= size)
        return;
    Node *tp = head;
    for(int i = 0;i < index;i++)
    {
        tp = tp->next;
    }
    Node *np = tp->next;
    tp->next = np->next;
    delete np;
    size--;
}

void List::RemoveByElement(const ElementType &element)
{
    Node *tp = head;
    while(tp->next)
    {
        if(tp->next->value == element)
        {
            Node* np = tp->next;
            tp->next = np->next;
            delete np;
            size--;
        }
        else
            tp = tp->next;
    }
}

ElementType *List::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    Node* tp = head;
    for(int i = 0;i < index;i++)
    {
        tp = tp->next;
    }
    return &tp->next->value;
}

void List::UpdateByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
        return;
    Node *tp = head->next;
    for(int i = 0;i < index;i++)
        tp =tp->next;
    tp->value = element;
}

void List::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    Node *tp = head->next;
    while(tp)
    {
        if(tp->value == oldvalue)
            tp->value = newvalue;
        tp = tp->next;
    }
}

void List::BuubleSort()
{
    for(int i = 0;i < size -1 ;i++)
    {
        Node *node = head;
        for(int j = 0;j < size - i - 1;j++)
        {
            if(node->next->value > node->next->next->value)
            {
                Node *tp = node->next;
                Node *np = tp->next;
                tp->next  =np->next;
                np->next = tp;
                node->next = np;
            }
        }
    }
}

void List::Sort()
{
    FastSort(head->next,nullptr);
}

ElementType *List::GetReserveIndex(size_t index)
{
    return nullptr;
}

List List::Merge(const List &list)
{
    List result;
    Node *tp = head->next;
    Node *np = list.head->next;
    while(tp && np)
    {
        if(tp->value < np->value)
        {
            result.InsertTail(tp->value);
            tp = tp->next;
        }
        else
        {
            result.InsertTail(np->value);
            np = np->next;
        }
    }
    while(tp)
    {
        result.InsertTail(tp->value);
        tp = tp->next;
    }
    while(np)
    {
        result.InsertTail(np->value);
        np = np->next;
    }
    return result;
}

List List::FdIntrSctn(const List &list)
{
    List result;
    Node *tp = head->next;
    Node *np = list.head->next;
    while(tp && np)
    {
        if(tp->value == np->value)
        {
            result.InsertTail(tp->value);
            tp = tp->next;
            np = np->next;
        }
        else if(tp->value < np->value)
        {
            tp = tp->next;
        }
        else if(tp->value > np->value)
        {
            np = np->next;
        }
    }
    return result;
}

List List::FindUnionSet(const List &list)
{
    List result;
    Node *tp = head->next;
    Node *np = list.head->next;
    while(tp && np)
    {
        if(tp->value == np->value)
        {
            result.InsertTail(tp->value);
            tp = tp->next;
            np = np->next;
        }
        else if(tp->value < np->value)
        {
            result.InsertTail(tp->value);
            tp = tp->next;
        }
        else if(tp->value > np->value)
        {
            result.InsertTail(np->value);
            np = np->next;
        }
    }
     while(tp)
    {
        result.InsertTail(tp->value);
        tp = tp->next;
    }
    while(np)
    {
        result.InsertTail(np->value);
        np = np->next;
    }
    return result;
}

List List::FindDifference(const List &list)
{
    List result;
    Node *tp = head->next;
    Node *np = list.head->next;
    while(tp && np)
    {
        if(tp->value == np->value)
        {
            tp = tp->next;
            np = np->next;
        }
        else if(tp->value < np->value)
        {
            result.InsertTail(tp->value);
            tp = tp->next;
        }
        else if(tp->value > np->value)
        {
            result.InsertTail(np->value);
            np = np->next;
        }
    }
     while(tp)
    {
        result.InsertTail(tp->value);
        tp = tp->next;
    }
    while(np)
    {
        result.InsertTail(np->value);
        np = np->next;
    }
    return result;
}

void List::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head;
    Node *Next = head->next;
    while(Next)
    {
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = Next->next;
    }
    cur->next = prev;
    head->next = cur;
}

void List::Reserve2()
{
    head->next = reserve(head->next);
}

void List::show()
{
}

void List::FastSort(Node *start, Node *end)
{
    if(start ==end)
        return;
    Node* slow = start;
    Node *fast = start->next;
    Node* temp = start;
    while(fast != end)
    {
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value,fast->value);
        }
        fast = fast->next;
    }
    std::swap(slow->value,temp->value);
    FastSort(start,slow);
    FastSort(slow->next,end);
}

List::Node *List::reserve(Node *node)
{
    if(node->next == nullptr)
        return node;
    else
    {
        Node *newHead = reserve(node->next);
        node->next->next = node;
        node->next = nullptr;
        return newHead;
    }
}
